package com.lie.prepare.algorithm.search;

import java.util.ArrayList;
import java.util.List;

import static com.lie.prepare.util.Print.*;

/**
 * Created by lie on 2018/4/12.
 *
 * 二分法
 * 二分法针对的是已经排好序的数据源
 * @see #doSearch(int[], int)  时间复杂度是O(log(n))，
 *
 * @see com.lie.prepare.algorithm.practise.ABS 玩了一下抽象
 */
public class BinarySearch {
    static int[] array = {1, 2, 4, 5, 6, 10, 20};


    public static void main(String[] args){
        List<Integer> keyList = new ArrayList<Integer>();
//        int key;
//        key = outOfArray();
//        key = -outOfArray();
//        key = inArray();
//        key = firstArray();
//        key = endArray();
//        print(doSearch(array, key));

        keyList.add(outOfArray());
        keyList.add(-outOfArray());
        keyList.add(inArray());
        keyList.add(firstArray());
        keyList.add(endArray());

        for (Integer k: keyList){
            print(doSearch(array, k));
        }
    }

    private static int outOfArray(){
        return 100;
    }
    private static int inArray(){
        return array[(array.length-1) /2];
    }
    private static int firstArray(){
        return array[0];
    }
    private static int endArray(){
        return array[array.length - 1];
    }

    public static int doSearch(int[] array, int key){

        int start =0, end = array.length -1;

        do {
            int half = (end+start) / 2;
            if (array[half] == key) {
                return half;
            } else if (array[half] < key) {
                start = half + 1;
//                print("start = "+ start);
            }else {
                end = half - 1;
//                print("end =" + end);
            }
        } while (end - start >= 0);

//        if (array[start] == key)
//            return start;
//
//        if (array[end] == key)
//            return end;

        return -1;
    }


}
